ABC 408E

位或不满足三角不等式的条件，因此不是 Dijkstra，别往那块想了，见下面这张图：

考虑位或运算最基本的性质：$a\mathrm{OR}1=1$。

见到位运算就要考虑拆位，直接如何令考虑最终答案的每一位尽可能取到 $0$。

正如提示三所说，我们直接考虑如何最小化答案：我们从高向低考虑答案二进制表示的每一位，对于第 $k$ 位，如果存在一条路径，其各条边权值二进制表示不仅满足已经确定的位的要求（当答案中某 $i>k$ 的位为 $0$ 时，该边权的第 $i$ 位就不得取 $1$），且第 $k$ 位均为 $0$，则答案的第 $k$ 位可以取为 $0$；反之，若不存在这样一条路径，代表答案的第 $k$ 位必须取为 $1$。由于不存在路径就等同于两节点不联通，判断连通性直接考虑并查集，当两个节点之间存在一条权值第 $k$ 位为 $0$ 的边时合并，处理完了后判断节点 $1$ 与节点 $n$ 的连通性，若不连通代表答案的第 $k$ 位为 $1$。

时间复杂度为 $\mathcal{O}(k\alpha (N)(N+M))$，式中 $k=\underset{i=1}{\overset{n}{max}}\lfloor {\log }_2{w}_i\rfloor$，即所有边权中最高的能取到 $1$ 的位数。